#ifndef __DESIGNLIST_H__
#define __DESIGNLIST_H__


/*
* leetcode 707 设计链表
* 实现 MyLinkedList 类
*/

class MyLinkedList {
    typedef struct Node {
        int Data;
        Node* next;
    }Node;

private:
    int Size;
    Node* Head;

public:
    MyLinkedList(): Size(0), Head(nullptr) {
        Head = new Node();
        Head->Data = -1;
        Head->next = nullptr;
    }

    ~MyLinkedList()
    {
        Node* cur = Head;
        while (cur != nullptr) {
            Node* temp = cur;
            cur = cur->next;
            delete temp;
        }
    }

    //获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
    int get(int index) {
        if (index >= Size)
            return -1;

        Node* cur = Head->next;
        for (int i = 0; i < index; i++, cur = cur->next);

        return cur->Data;
    }

    //将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    void addAtHead(int val) {
        Node* node = new Node();
        node->Data = val;

        node->next = Head->next;
        Head->next = node;

        Size++;
    }

    //将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    void addAtTail(int val) {
        Node* cur = Head;
        while (cur->next != nullptr)
            cur = cur->next;

        Node* node = new Node();
        node->Data = val;

        node->next = nullptr;
        cur->next = node;

        Size++;
    }

    //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
    //如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
    //如果 index 比长度更大，该节点将 不会插入 到链表中
    void addAtIndex(int index, int val) {
        if (index >= Size)
            return;

        Node* cur = Head;   //与其他遍历不同, 从 Head 节点而不是从 Head->next (这样会得到遍历结果的前一个节点)
        for (int i = 0; i < index; i++, cur = cur->next);

        Node* node = new Node();
        node->Data = val;

        node->next = cur->next;
        cur->next = node;

        Size++;
    }

    //如果下标有效，则删除链表中下标为 index 的节点。
    void deleteAtIndex(int index) {
        if (index >= Size)
            return;

        Node* pre = Head;
        Node* cur = Head->next;
        for (int i = 0; i < index; i++, pre = pre->next, cur = cur->next);

        pre->next = cur->next;
        cur->next = nullptr;
        delete cur;

        Size--;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

#endif // !__DESIGNLIST_H__


